We study the sparsity and optimality properties of crowd navigation and findthat existing techniques do not satisfy both criteria simultaneously: eitherthey achieve optimality with a prohibitive number of samples or tractabilityassumptions make them fragile to catastrophe. For example, if the human androbot are modeled independently, then tractability is attained but the planneris prone to overcautious or overaggressive behavior. For sampling based motionplanning of joint human-robot cost functions, for $n_t$ agents and $T$ steplookahead, $\mathcal O(2^{2n_t T})$ samples are needed for coverage of theaction space. Advanced approaches statically partition the action space intofree-space and then sample in those convex regions. However, if the human is\emph{moving} into free-space, then the partition is misleading and sampling isunsafe: free space will soon be occupied. We diagnose the cause of thesedeficiencies---optimization happens over \emph{trajectory} space---and proposea novel solution: optimize over trajectory \emph{distribution} space by using aGaussian process (GP) basis. We exploit the "kernel trick" of GPs, where acontinuum of trajectories are captured with a mean and covariance function. Byusing the mean and covariance as proxies for a trajectory family we reasonabout collective trajectory behavior without resorting to sampling. The GPbasis is sparse and optimal with respect to collision avoidance and robot andcrowd intention and flexibility. GP sparsity leans heavily on the insight thatjoint action space decomposes into free regions; however, the decompositioncontains feasible solutions only if the partition is dynamically generated. Wecall our approach \emph{$\mathcal O(2^{n_t})$-sparse interacting Gaussianprocesses}.
展开▼
